package com.gaofeng.algo.java;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class DeepSearchJava {

    public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int answer = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) { //遍历图中所有的顶点
                int curArea = 0;
                Deque<Integer> stacki = new LinkedList<>();
                Deque<Integer> stackj = new LinkedList<>();
                stacki.push(i);
                stackj.push(j); //将顶点入栈,标记其是否被遍历过
                while (!stacki.isEmpty()) {  //
                    int curri = stacki.pop();
                    int currj = stackj.pop();
                    //如果当前顶点不满足条件,就跳过
                    if (curri < 0 || currj < 0 || curri == m || currj == n || grid[curri][currj] != 1) {
                        continue;
                    }
                    curArea++;
                    //满足条件了,说明当前顶点被遍历过
                    grid[curri][currj] = 0;
                    int[] directionsi = {0, 0, 1, -1};
                    int[] directionsy = {1, -1, 0, 0};

                    //搜索的下一步的走向添加到栈中
                    for (int k = 0; k < directionsi.length; k++) {
                        int nextI = curri + directionsi[k];
                        int nextJ = currj + directionsy[k];
                        stacki.push(nextI);
                        stackj.push(nextJ);
                    }
                }
                //取出每一次顶点搜索后的最大值
                answer = Math.max(answer, curArea);
            }
        }
        return answer;
    }

    public int findCircleNum(int[][] M) {
        int size = M.length;
        int[] visited = new int[size];
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }

    private void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }

    int[] directions = new int[]{-1, 0, 1, 0, -1};

    /**
     * 左上是太平洋
     * 右下是大西洋
     * @param matrix
     * @return
     */
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> ans = new ArrayList<>();
        int m = matrix.length;
        if (m == 0 || matrix[0].length == 0) {
            return ans;
        }
        int n = matrix[0].length;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            //从左边出发的顶点要能够到达太平洋
            dfs(matrix, canReachP, i, 0);
            //从右边出发的顶点要能够到达大西洋
            dfs(matrix, canReachA, i, n - 1);
        }

        for (int i = 0; i < n; i++) {
            //从上边出发的顶点能够到达太平洋
            dfs(matrix, canReachP, 0, i);
            //从下面出发的顶点能够到达大西洋
            dfs(matrix, canReachA, m - 1, i);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachA[i][j] && canReachP[i][j]) {
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(i);
                    tempList.add(j);
                    ans.add(tempList);
                }
            }
        }
        return ans;
    }

    /**
     * i和j 确定了当前的位置,也就是顶点.
     * 默认情况下,每一个顶点都是不可达的
     * 当遍历时,就把当前顶点标记为true,表示遍历过,
     * 然后从当前顶点的四个方向开始进行深搜
     * 顶点可以进行下一次的深搜的条件是
     * 顶点的位置在边界内,并且满足当前顶点的值,小于等于下一次顶点的值.表示水可以逆着往这个方向流.
     *
     * 递归上来的判断条件是,如果当前顶点可达,表明遍历过,可以直接返回.
     *
     * @param matrix
     * @param canReach
     * @param i
     * @param j
     */
    private void dfs(int[][] matrix, boolean[][] canReach, int i, int j) {
        if (canReach[i][j]) {
            return;
        }
        canReach[i][j] = true;
        int x, y;
        for (int k = 0; k < 4; k++) {
            x = i + directions[k];
            y = j + directions[k + 1];
            if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[i][j] <= matrix[x][y]) {
                dfs(matrix, canReach, x, y);
            }
        }
    }

}
